#include <bits/stdc++.h>
using namespace std;

/*
2145. 统计隐藏数组数目
已解答
中等
相关标签
相关企业
提示
给你一个下标从 0 开始且长度为 n 的整数数组 differences ，它表示一个长度为 n + 1 的 隐藏 数组 相邻 元素之间的 差值 。更正式的表述为：我们将隐藏数组记作 hidden ，那么 differences[i] = hidden[i + 1] - hidden[i] 。

同时给你两个整数 lower 和 upper ，它们表示隐藏数组中所有数字的值都在 闭 区间 [lower, upper] 之间。

比方说，differences = [1, -3, 4] ，lower = 1 ，upper = 6 ，那么隐藏数组是一个长度为 4 且所有值都在 1 和 6 （包含两者）之间的数组。
[3, 4, 1, 5] 和 [4, 5, 2, 6] 都是符合要求的隐藏数组。
[5, 6, 3, 7] 不符合要求，因为它包含大于 6 的元素。
[1, 2, 3, 4] 不符合要求，因为相邻元素的差值不符合给定数据。
请你返回 符合 要求的隐藏数组的数目。如果没有符合要求的隐藏数组，请返回 0 。

 

示例 1：

输入：differences = [1,-3,4], lower = 1, upper = 6
输出：2
解释：符合要求的隐藏数组为：
- [3, 4, 1, 5]
- [4, 5, 2, 6]
所以返回 2 。
示例 2：

输入：differences = [3,-4,5,1,-2], lower = -4, upper = 5
输出：4
解释：符合要求的隐藏数组为：
- [-3, 0, -4, 1, 2, 0]
- [-2, 1, -3, 2, 3, 1]
- [-1, 2, -2, 3, 4, 2]
- [0, 3, -1, 4, 5, 3]
所以返回 4 。
示例 3：

输入：differences = [4,-7,2], lower = 3, upper = 6
输出：0
解释：没有符合要求的隐藏数组，所以返回 0 。
 

提示：

n == differences.length
1 <= n <= 105
-105 <= differences[i] <= 105
-105 <= lower <= upper <= 105
*/

// 法一
class Solution {
	public:
	using ll = long long;
	int numberOfArrays(vector<int>& differences, int lower, int upper) {
		ll cur_sum = 0;
		ll max_prefix = 0; //最大前缀和
		ll min_prefix = 0; //最小前缀和
		for (int dif : differences) {
			cur_sum += dif;
			max_prefix = max(max_prefix, cur_sum);
			min_prefix = min(min_prefix, cur_sum);
		}

		ll a0_min = max((ll)lower, lower - min_prefix);
		ll a0_max = min((ll)upper, upper - max_prefix);
		ll ans = a0_max - a0_min + 1;

		return ans > 0 ? ans : 0;
	}
};

// 不同写法
class Solution {
	public:
	int numberOfArrays(vector<int>& differences, int lower, int upper) {
		//计算某一个连续段的最大值
		int n = differences.size();
		long long min_d = 0; //最小前缀和
		long long max_d = 0; //最大前缀和
		long long d = 0;
		for(auto diff:differences){
			d+=diff;
			if(d<min_d){
				min_d = d;
			}
			if(d>max_d){
				max_d = d;
			}
		}
		if((upper-lower+1)-(max_d-min_d)>0){
			return (upper-lower+1)-(max_d-min_d);
		}
		else{
			return 0;
		}
	}
};
